A cache memory is a high-speed memory which speeds up CPU memory accesses by storing certain sections of the main memory. The cache memory responds to CPU memory cycles when CPU memory cycles are directed towards locations previously stored in the cache. Caches are in a level of the memory hierarchy between the CPU and main memory and takes advantage of its locality of access. Cache memory typically comprises dynamic random access memory (DRAM), static random access memory (SRAM), or other memory devices. Data stored in a cache memory is organized into data sets which are commonly referred to as cache lines or data lines.
Restrictions on where a block of data is placed in a cache create three categories of cache organization. If each block of data has only one place it can appear in the cache, the cache is said to be direct mapped. The mapping is usually the block-frame address modulo the number of blocks in the cache. If a block of data can be placed anywhere in the cache, the cache is said to be fully associative. If a block of data can be placed in a restrictive set of places in the cache, the cache is said to be set associative. A set is a group of two or more blocks in the cache. The block of data is first mapped onto a set. Then, the block of data can be placed anywhere within the set. The set is usually chosen by bit selection such as block-frame address modulo the number of sets in the cache. If there are n blocks in a set, the cache placement is called n-way set associative.
Cache designs typically require tag random access memory (RAM) to record information specifying which memory sections are stored within the cache. Usually, only a certain portion of the address is stored within the tag RAM. A tag entry called a tag address is compared against the corresponding address portion of the current memory cycle in order to determine whether a match occurred. This process is, called a cache look-up. The tag address of every cache block that might contain the desired information is checked to see if it matches the block-frame address from the CPU. All possible tags are typically searched in parallel since speed is of the essence.
When a cache look-up is successful a cache hit occurs. Certain cache implementations require another tag entry called a valid bit. A valid bit qualifies a cache look-up such that a cache hit occurs only when the valid bit is set. The valid bit is typically added to the address tag to indicate whether or not a specific entry contains a valid address. There are several instances where the address tag may represent an invalid address. For example, when a processor starts up, the cache is empty. Thus, the tag address fields corresponding to cache locations are invalid. Another example of an instance where an address tag may represent an invalid address is when memory is updated with new data. In this situation, the corresponding cache locations containing outdated information should not be accessed despite the fact that the tag address corresponds to an area of memory. In these instances, the cache controller needs to be informed that the specific cache location is not valid, although previously cached to avoid cache coherency problems. Thus implementation of a valid bit indicates whether an entry contains a valid address. If the bit is not set, the cache controller realizes no hit can occur on this address.
The traditional way of implementing a valid tag entry is the allocation of one tag RAM bit for each cache location. The allocated bit defines whether the cache location is in a valid or invalid state. The penalty that a system designer pays for the valid/invalid state in the traditional approach is the fact that the tag RAM needs to be one bit wider for a given cacheability range.
Thus, a more efficient apparatus and method for indicating whether data stored in a cache memory location is valid is needed.